1. The Field of the Invention
The present invention relates to a system and method for manipulating control data used to generate outlines of graphical objects. More specifically, the present invention relates to a system and method for iteratively solving constraints in a font-hinting language.
2. Background and Related Art
Computing technology has transformed the way we work and play. Computing systems now take a wide variety of forms including desktop computers, laptop computers, tablet PCs, Personal Digital Assistants (PDAs), and the like. Even household devices (such as refrigerators, ovens, sewing machines, security systems, and the like) have varying levels of processing capability and thus may be considered computing systems. As time moves forward, processing capability may be incorporated into a number of devices that traditionally did not have processing capability. Accordingly, the diversity of computing systems may likely increase.
Almost all computing systems that interface with human beings use a display to convey information. In many cases, the appeal of the display is considered an important attribute of the computing system. Historically, textual information (e.g., Latin-based characters) was displayed in cells of a Cathode Ray Tube (“CRT”) display device. Each cell was divided into a grid of equally sized grid positions wherein each grid position could be turned on or off. For example, each cell of a CRT could be an 8×8 grid resulting in 64 possible grid positions per cell.
Each character of a character set was stored as a memory image (a bit-map) in the hardware of the CRT display device (e.g., in the video adapter). A memory image included a number of binary values (e.g., 64 binary values for displaying a character on an 8×8 grid), where each binary value corresponded to a specified grid position. One value (e.g., binary “1”) represented that a corresponding grid position was to be “on” when the character was displayed and another value (e.g., a binary “0”) represented that a corresponding grid position was to be “off” when the character was displayed. Upon receiving binary data (e.g., a bit-map) representing a character, the CRT would “turn on” grid positions corresponding to a binary 1 and would “turn off” grid positions corresponding to a binary 0 to display the character.
More recently, some computing systems have used proportional bit-maps (e.g., stored on disk) that vary in cell size depending on the character that is to be displayed. For example, in a proportional bit-map character set, the cell for the letter “i” could be more narrow (e.g., width of 3 grid positions) than the cell for the letter “h” (e.g., width of 6 grid positions).
However, storing characters as bit-maps (either fixed or proportional) can consume significant computing system resources. Since a computing system may need to display and print characters of a font (typically 256 or more different characters) at a variety of different sizes, storage of a significant number of different sized bit-maps may be required. For example, it may desirable to have a word processor display and print characters of a font in sizes ranging from 4 pt to 72 pt. Thus, a computing system running the word processor would potentially have to store 68 (72 minus 4) different sizes of bit-maps for displaying the font at different sizes.
Further, since printers typically have different (and for the most part higher) resolution than displays, the computing system would potentially also have to store a corresponding 68 (72 minus 4) different sizes of bit-maps for printing the font at different sizes. For example, a bitmap of an 8×5 grid (requiring 40 bits of storage) may be used to display a character at a specified size, while a bit-map of a 50×30 grid (requiring 1500 bits of storage) is used to print the character at the specified size.
The storage requirement problems associated with bit-map fonts is further compounded when a computing device is to display and print characters from different fonts. That is, the computing device may need to store bit-maps for representing a variety of different fonts at a variety of different sizes. Thus, in the above example, configuring the word processor to use 50 different fonts could result in well over 5,000 different sets of bit-maps (e.g., (68+68)*50). Since many character sets include 256 or more characters, this could easily result over 1 million individual bit-maps (e.g., 5,000*256). Storing bit-maps for underlined, bold, and/or italicized versions of each font can further increase the storage requirements. Further, producing a large number of bitmaps by hand is extremely time consuming.
Accordingly, even more recently, graphics primitives have been used to describe characters of a font. For example, a set of control points and instructions for connecting the points (e.g., connect with a straight line, an arc, a Bezier, etc.) can be used to define the outline of a character in an arbitrary grid space (e.g., an arbitrary grid space greater than the highest resolution of a pixelated device. Often, characters will be described at larger size and then mathematically scaled down (or otherwise manipulated) when the characters are to be rendered at smaller sizes (or as bold, italic, etc.). Thus, a reduced number of descriptions, and potentially only one description, for a character (per font) need be stored.
To scale a character down the location of control points can be divided by a scaling factor. For example, to scale a character down by a scaling factor of 10, the coordinates of each control point defining the character (at the higher resolution) can be divided by 10. It may be that control points defining a character for display on a 100×100 grid are to be scaled down for display on a 10×10 grid. Thus, a control point at grid position (50, 30) can be scaled down to a control point at grid position (5, 3), a control point at grid position (70, 70) can be scaled down to a control point at grid position (7, 7), etc. Accordingly, a smaller outline representing the character may be calculated and there is a reduced need for storing a number of different sizes of bit-maps for the character.
The smaller outline can then be analyzed to identify grid locations that are to be turned on and to identify grid locations that are to be turned off (a process often referred to as “scan conversion”). One scan conversion algorithm determines if the center of a grid position is inside or outside the smaller outline. When the center of a grid position is inside the smaller outline the grid position is turned on. On the other hand, when the center of a grid position is outside the smaller outline the grid position is turned off.
Also, when rendering a character, portions of the character may be required to ce conform to one or more constraints. A constraint can be expressed as algorithm defining one or more dependent parameters in terms of one or more independent parameters. Constraints for one control point can be expressed in terms of the location of other control points or locations on a grid (e.g., a capitalization line). For example, the position of a control point “P” can be expressed in terms of the position of a control point “Q” such that the P is a fixed distance “c” from Q. That is, P=Q+c. Thus, when Q is moved, a corresponding move of P may be required so that P conforms to the fixed distance c.
Due in part to the wide variety of different artistic and technical features in different fonts, constraints can be tailored to an individual font. Often, constraints are expressed in terms of a font-hinting language (e.g., the TrueType® language) having a limited and highly specific vocabulary. The limited and highly specific vocabulary simplifies the translation of the mathematical concepts into the font-hinting language. For example, it would typically be straight forward to translate the above mentioned constraint (P=Q+c), since font-hinting languages typically include an assignment operator (e.g., “=”) and an addition operator (e.g., “+”).
However, the limited and highly specific vocabulary can also limit the types of the constraints that can be expressed. For example, it can be difficult to express a constraint based on a more complex mathematical function, such as, for example, a transcendental function, because these more complex mathematical functions are not included in font-hinting language vocabularies and can be difficult to add. Lack of more complex mathematical functions (e.g., a square root function) can in turn make it difficult to determine appropriate control point locations for complying with constraints. Therefore, what would be advantageous are mechanisms for using the existing vocabulary of font-hinting languages to solve constraints even when the font-hinting languages lack more complex vocabulary.